1. Field of the Invention
The present invention relates to a divider for performing signed division using a redundant signed digit (hereafter referred to as RSD).
2. Description of the Prior Art
The following is the brief description of the operation using RSD (Redundant Signed Digit).
In the RSD notation, the numeral X is expressed as the finite difference of two numerals x* and x**. That is, RSD is a numeral defined as follows: ##EQU1## Where, EQU x.sub.i.sup.*, x.sub.i.sup.** .epsilon.(0,1)
In this case, x1 definitely equals x.sub.i .epsilon. (1,0, 1 (reversed)).
For an RSD-notation numeral, each digit takes three values of 1, 0, and 1 (reversed) (minus 1). For normal binary notation or complement-of-2 notation, the notation of a numeral has only one way. For the RSD notation, however, a plurality of notations are possible, in other words, there is redundancy. For example, the numeral 7 is expressed by four-digit RSD as {0111}, {1001 (reversed)}, (101 (reversed) 1}, and {11 (reversed) 11}.
Addition and subtraction between RSD-notation numeral X and normal unsigned binary number are described below. In this case, the following are assumed. ##EQU2## Where, EQU y.sub.i.sup.*, y.sub.i.sup.** .epsilon.(1,0) ##EQU3## Where, EQU z.sub.i .epsilon.(1,0)
When assuming the sum of Y and Z as: ##EQU4## Where, EQU s.sub.i.sup.*, s.sub.ii.sup.** .epsilon.(1,0)
And, when assuming the difference between Y and Z as: ##EQU5## Where, EQU d.sub.i.sup.*, d.sub.i.sup.** .epsilon.(1,0)
Each operation is performed as shown in FIGS. 4 and 5. In FIGS. 4 and 5, 1a to 1d are a full adder and a small circle represents reversal of input and output. FIG. 6 shows a truth table of the full adder.
Moreover, addition and subtraction between a numeral expressed by RSD and a numeral expressed by complement of 2 are described below.
FIG. 9 shows the addition between a numeral expressed by RSD and a numeral expressed by complement of 2. The result of the addition is obtained as a numeral expressed by RSD. In this case, Y is an augend expressed by RSD, Z is an addend expressed by complement of 2, and S is an addition result expressed by RSD. Y and S are shown by the above expressions (2) and (4); and the following is assumed: ##EQU6## In FIG. 9, 1a to 1e are a type of generalized full adders. FIG. 10 shows a truth table of the full adder.
FIG. 11 shows the subtraction between a numeral expressed by RSD and a numeral expressed by complement of 2. The result of this subtraction is obtained as a numeral expressed by RSD. In this case, Y is a minuend expressed by RSD, Z is a subtrahend expressed by complement of 2, and S is a subtraction result expressed by RSD.
The following is the description of addition of "72+21 =93" and subtraction of "72-21=51". Because 72 equals 11 (reversed) 011 (reversed) 000 (RSD notation), 93 is obtained as an addition result through the operation shown in FIG. 12 and 51 is obtained as an subtraction result through the operation shown in FIG. 13. From FIGS. 12 and 13, it is found that addition or subtraction between a numeral expressed by RSD and a numeral expressed by complement of 2 can be executed for the same time as the delay of full adder because carrier propagation is unnecessary.
The following is the description of division. The division between a numeral expressed by RSD and a numeral expressed by complement of 2 is, in a word, the irreparable-type division using RSD notation for a dividend and complement-of-2 notation for a divisor. For the irreparable-type division, there is a little degree of freedom in selection of quotient digit. Therefore, when considering that the quotient digit can be determined at a high speed, it is significant to use numerals expressed by RSD in order to perform high-speed addition and subtraction.
The following is the description of the algorithm for division between a numeral expressed by RSD and a numeral expressed by complement of 2.
For the irreparable-type division, the quotient digit "qj" is selected among 1 and 1 (reversed) so that the following expressions (6) and (7) are satisfied. EQU R.sup.j+1 =2.multidot.(R.sup.j -q.sub.j .multidot.D) (6) EQU -2 D &lt;R.sup.j+1 &lt;2 D (7)
In this case, Rj is partial remainder and D is a divisor qj is the j-th digit of a quotient. For the division in accordance with RSD, the dividend R.sup.0 is expressed by RSD and the divisor D is expressed by complement of 2. That is, R.sup.0 and D are expressed as follows: ##EQU7## Where, EQU r.sub.0.sup.0 =0, r.sub.i.sup.0 .epsilon.(1,0,1), r.sub.i.sup.0*, r.sub.i.sup.0** .epsilon.(1,0) ##EQU8## Where, EQU d.sub.0 .noteq.d.sub.i, d.sub.i .epsilon.(0,1)
Moreover, the j-th digit "qj" of the quotient is selected as shown in the truth table in FIG. 7 so as to meet the above expressions (6) and (7) and the following expression. ##EQU9## Where, EQU r.sub.i.sup.j+1 .epsilon.(1,0,1),r.sub.i.sup.j+1*, r.sub.i.sup.j+1** .epsilon.(1,0)
Though 0 and 0 (reversed) are equal as a numerical value, they differ in their corresponding operations.
The following is the description of the above division algorithm. For the division between a numeral expressed by RSD and a numeral expressed by complement of 2, the dividend R.sup.0 and the divisor D are expressed as shown in the above expressions (8) and (9) (however, r.sub.0.sup.0 =0 0.sup.r, r.sub.0.sup.0** =0, d.sub.0 .noteq.d.sub.1 and the quotient digit "qj" is selected among 1, 0, 0 (reversed), and 1 (reversed). Though 0 (reversed) is the same as 0, they differ in their corresponding operations. FIG. 14 shows the operation corresponding to each quotient digit. To meet the above expression (10) through the operation, r.sub.i.sup.j+1 must be equal to 0 or r.sub.i.sup.j+1* must be equal to r.sub.i.sup.j+1** when "i" is smaller than 0. To make the above condition effective, it is only necessary to select the quotient digit "qj" in accordance with the high-order three bits of R.sup.j --r.sub.0.sup.j, and r.sub.1.sup.j, and r.sub.2.sup.j or r.sub.0.sup.j*, r.sub.0.sup.j**, r.sub.1.sup.j*, r.sub.1.sup.j** , r.sub.2.sup.j*, and r.sub.2.sup.j**. FIG. 15 shows a decision table for the above selection. In the decision table, r.sub.0, r.sub.1, and r.sub.2 shows the high-order three bits of R.sup.j and "qj" shows the quotient digit to be selected.
As described above, the division between a numeral expressed by RSD and a numeral expressed by complement of 2 may be executed at a very high speed when considering that the quotient digit in each cycle can be determined only by checking the high-order three bits of partial remainder and the operation does not require carry propagation.
The following is the description of an existing divider for performing division in accordance with the above RSD by referring to FIG. 16. In FIG. 16, numerals 2 and 3 are an (n+1)-bit register, 4 and 5 are an (n+1)-bit data latch, 6 is an (n+1)-bit register, 7 is a selector, 8 is an adder, 9 and 10 are an m-bit shift register, 11 and 12 are a shifter, 13 is a bit processing means for outputting the quotient digit r.sub.n * and the selection signal SEL for the selector in accordance with the truth table in FIG. 7 depending on the contents of respective high-order three bits of the registers 2 and 3 and the contents of the most significant bit of the register 6, 14 is a quotient digit determining means for determining the quotient digit when respective high-order three bits of the registers 2 and 3 and the most significant bit of the register 6 are set to "0" in accordance with the truth table in FIG. 7, 15 is a quotient digit correcting means for correcting the output of the quotient digit determining means depending on the contents of the most significant bit of the register 6, and 16 and 17 are a shift register for storing quotient digits.
The outputs of the registers 2 and 3 are input to the data latches 4 and 5 respectively through (n+1) electric switches not illustrated. The selector 7 outputs a signal in which all bits of the output of the register 6 are 1, a signal in which all bits of it are 0, or a signal in which all bits of it are reversed by selecting it with the selection signal SEL. The shifters 11 and 12 receive the outputs of the shift registers 9 and 10 as the least significant bit respectively and shift the output of the adder 8 by one bit in the direction of the most significant bit. The outputs of the shifters 11 and 12 are input to the registers 2 and 3 respectively through (n+1) electric switches not illustrated.
The following is the description of the operation of the existing divider. For easy understanding of the description of the operation, it is assumed that the dividend R is divided into R.sup.** and R.sup.*, high-order (n+1) bits of R.sup.** and R.sup.* are stored in the registers 2 and 3 respectively, low-order m bits of them are stored in the shift registers 9 and 10 respectively, and the divisor D is stored in the register 6.
First, the contents of the high-order (n+1) bits of R.sup.** and those of the high-order (n+1) bits of R.sup.* which are stored in the registers 2 and 3 respectively are sent to and held by the data latches 4 and 5. At the same time, the contents of the high-order three bits of R.sup.** and those of the high-order three bits of R.sup.* are sent to the bit processing means. The quotient determining means 14 decodes these 6 bits to determine a quotient digit for D&gt;0 in accordance with the truth table in FIG. 7. The quotient digit correcting means 15 receives the quotient digit to correct it to "1 (reversed)" if the quotient digit is "1" for D&lt;0 and to "1 (reversed)" if it is 1 (reversed) for D&lt;0. The bit processing means 13 determines r.sub.n.sup.* in accordance with the quotient digits q.sup.** and q.sup.* corrected by the quotient digit correcting means 15, outputs q.sup.** and q.sup.* to the shift registers 16 and 17 respectively and also to the selector 7 as the selection signal SEL, and outputs r.sub.n.sup.* to the adder 8. The selector 7 selects an input among four operations in FIG. 8 by the selection signal SEL so that the operation performed by the adder 8 corresponds to the contents of quotient digit and outputs the input to the adder 8. The adder 8 executes any one of the operations in FIG. 8 by the (n+1)-bit RSD-notation numeral expressed by the high-order (n+1) bits of R.sup.** and R.sup.* held by the data latches 4 and 5, the output of the selector 7, and r.sub.n.sup.* outputt by the bit processing means 13. For the operation result, the following expression is always effected. EQU r.sub.-2.sup.** =r.sub.-2.sup.*, r.sub.-1.sup.** =r.sub.-1.sup.* ( 11)
Remaining r.sub.0.sup.** to r.sub.n-1.sup.** and r.sub.0.sup.* through r.sub.n-1.sup.* are input to the shifters 11 and 12 respectively. The outputs of the shift registers 9 and 10 are input to the shifters 11 and 12 respectively as the least significant bit. These are added with r.sub.0.sup.** to r.sub.n-1.sup.** and r.sub.0 * to r.sub.n-1.sup.** to serve as the inputs of the registers 2 and 3.
By assuming the above operation as one cycle, quotients are obtained in the shift registers 16 and 17 after (m+1) cycles are executed. Remainders are stored in the registers 2 and 3 by shifting one bit to the left.